#include "stc.h"
#define SIZE 100

struct Stack { 
	char data[SIZE]; 
	int top; 
} s;

void initStack(Stack &s)
{
	s.top = 0;
}

bool Push (Stack &s ,char data){
	if(s.top == SIZE)
		return false;
	s.top++;
	s.data[s.top] = data ;
	return true ;
}

char Pop (Stack &s ){
	if(s.top== 0)
		return 0;
	char c = s.data[s.top];
	s.top--;
	return  c;
}

bool isEmpty(Stack &s)
{
	if(s.top == 0)
		return true;
	return false;
}

void copyStr(char *str1, char *str2)
{
	while(*str2 != 0)
	{
		*str1 = *str2;
		str1++;
		str2++;
	}
	*str1 = '\0';
}

int lenStr(char *str)
{
	int len = 0;
	while(*str != 0)
	{
		len++;
		str++;
	}
	return len;
}

int power(int n)
{
	int result = 1;
	for(int i = 0; i < n; i++)
	{
		result = result*10;
	}
	return result;
}

int convertString2Int(char *str)
{
	int p = lenStr(str)-1;
	int result = 0;
	int a;
	while(*str != 0)
	{
		a = ((int) *str)-48;
		result = result + a*power(p);
		p--;
		str++;
	}
	PutInt(result);
	return result;
}

char* getStr()
{
	char* input = new char[50];
	char c = 0;
	int count = 0;
	char arrInput[50];
	while(true)
	{
		c = GetChar();
		if (c != 13)
		{
			arrInput[count] = c;
			PutChar(arrInput[count]);
			count++;
		}
		if(c == 8)
		{
			if(count > 0)
			{
				PutStr(" \b");
				count = count - 2;
			}
		}

		if((c == 13 && count > 0) || count >= 50)
			break;
	}
	arrInput[count] = '\0';
	copyStr(input, arrInput);
	return input;
}

bool isNumber(char c)
{
	int code = (int) c;
	if((code-48) >= 0 && (code-48) <= 9)
		return true;
	return false;
}

void convertInfix2Posfix(char *infix, char *posfix)
{
	int len = lenStr(infix);
	int index = 0;
	char c, pc;
	for(int i = 0; i <= len; i++)
	{
		c = infix[i];
		if(isNumber(c) || c == ' ')
		{
			posfix[index] = c;
			index++;
		}

		else if(c == '+' || c == '-')
		{
			if(!isEmpty(s) && s.data[s.top] != '(')
			{
				pc = Pop(s);
				posfix[index] = pc;
				index++;
			}
			Push(s, c);
			posfix[index] = ' ';
			index++;
		}

		else if(c == '(')
		{
			Push(s, c);
		}
		else if(c == ')')
		{
			while(!isEmpty(s) && s.data[s.top] != '(')
			{
				pc = Pop(s);
				posfix[index] = pc;
				index++;
			}
			pc = Pop(s);
		}
	}

	while(!isEmpty(s))
	{
		pc = Pop(s);
		posfix[index] = pc;
		index++;
	}
	posfix[index] = '\0';
	PutStr("\n");
	PutStr(posfix);
}
char* subString(char *s, int start, int end)
{
}

int caculate(char posfix[100])
{
	int len = lenStr(posfix);
	return 0;
}

void main()
{
	initStack(s);
	char *infix = new char[100];
	char *posfix = new char[100];
	PutStr("\nExpression>");
	copyStr(infix, getStr());
	convertInfix2Posfix(infix, posfix);
	caculate(posfix);
	PutStr("\nResult :");
	PutStr(posfix);

	return;
}